1. Technical Field
Nodes in a computer network can also function as encoders. In particular, a node operating as encoder does not just relay or replicate information received from an input link (switch behavior), it also encodes such information. Coding at a node in a network is known as network coding.
2. Description of the Prior Art
Throughout the description of the present disclosure, reference will be made to the enclosed Annexes A1, A2, A3 and A4, which make part of the present disclosure.
Network coding enables connections that are not possible with just routing. In particular, it has been shown R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network Information Flow”, IEEE Transactions on Information Theory, vol. 46, pp. 1204-1216 (2000), that it is in general not optimal to simply route or replicate the information to be multicast. Rather, by employing coding at the nodes, bandwidth can generally be saved.
A network can be represented as a directed graph, as shown in R. Koetter and M. Medard, “Beyond Routing: An Algebraic Approach to Network Coding”, Proceedings of the 2002 IEEE Infocom (2002). The graph comprises source nodes and receiver nodes, where discrete independent random processes (source processes) are observable at one or more of the source nodes and output processes are observable at the receiver nodes. In the above reference, an algorithm for finding a linear coding solution to a given multicast problem, using knowledge of the entire network topology is disclosed.
However, in applications where communication is limited or expensive, it may be preferable to determine each node's behavior in a distributed manner.